package com.ljy.my_study.leetcode.丑数II;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/** 
* @author James
* @date 2018年9月18日 
*/
public class TestMain2 {
	
	public static void main(String[] args) {
		TestMain testMain=new TestMain();
		System.out.println(testMain.nthUglyNumber(122));
		System.out.println("---------------------------");
		TestMain2 testMain2=new TestMain2();
		System.out.println(testMain2.nthUglyNumber(122));
	}
	
	public int nthUglyNumber(int n) {
		if(n==1) {
			return 1;
		}
		int[] arr= {2,3,4,5};
		if(n<=5) {
			return arr[n-2];
		}
		int startIndex=0;
		int count=5;
		List<Integer> list=new ArrayList<>();
		list.add(2);
		list.add(3);
		list.add(4);
		list.add(5);
		Set<Integer> set=new HashSet<>();
		do {
			set.clear();
			for(int i=0;i<list.size();i++) {
				for(int j=0;j<arr.length;j++) {
					set.add(list.get(i)*arr[j]);
				}
			}
			list.clear();
			list.addAll(set);
			Collections.sort(list);
			startIndex=count;
			count+=set.size();
			if(n<=count) {
				return list.get(n-startIndex);
			}
		}while(n>count);
		return 0;
	}
}
